Driven by increasing usage of a variety of network applications, such as those involving the Internet, computer networks are of increasing interest. FIG. 1A depicts a computer network 1 as coupled to the Internet 30. The computer network 1 includes gateways 12 and 25 as well as switches 10 and 14. The switches 10 and 14 are coupled to hosts 2, 4 and 6 and hosts 16 and 18, respectively. The switches 10 and 14 are also coupled to servers 7 and 8 and server 20, respectively.
The switches 10 and 14 are often used to couple portions of the network 1 together, as well as to couple different networks together. FIG. 1B depicts a high-level block diagram of a switch 10 which can be used in a computer network such as the network 1. The switch 10 includes a switch fabric 43 coupled with blades 47, 48 and 49. Each blade 47, 48 and 49 is generally a circuit board and includes at least a network processor 42 coupled with ports 44. Thus, the ports 44 are coupled with hosts (not shown in FIG. 1B). The blades 47, 48 and 49 can provide traffic to the switch fabric 43 and accept traffic from the switch fabric 43. Thus, any host connected with one of the blades 47, 48 or 49 can communicate with another host connected to another blade 47, 48 or 49 or connected to the same blade. Although shown only in the switch 10, the network processor 42 may also be used in a router or other mechanism for transmitting packets.
In order to transmit traffic through the network 1, the addresses of the destinations for data packets utilized. Typically, the data packets are IP packets (“packet”), each of which has an IP address. The IP address, which is thirty-two bits long, is typically used for determining how to route the packet. The IP address, hereinafter termed the key, is then compared to a set of known addresses by the network processor 42 in order to determine the destination and how to forward the packet. This comparison is made using a longest prefix match search, which finds the closest match to the key from a set of stored addresses available to the network processor 42.
FIG. 2 depicts a conventional method 50 for forwarding a packet using a longest prefix match. The method 50 is typically used by a network processor 42 that resides in a switch, router or other component that forwards packets. A search of a tree including stored addresses is performed in order to find the longest prefix match, via step 52. The longest prefix match is a stored address which is the closest match to the key. The longest prefix match need not be an exact match for the key. The longest prefix match is typically the stored address which matches the most significant bits of the key. The type of tree used in step 52 is typically a Patricia tree. The search performed in step 52 typically searches bit by bit. For example, a first bit of the key is tested to determine its value. Based on the outcome of the test of a particular bit, if the bit is a one or a zero, another bit is tested. This process continues until the stored address that matches the most bits of the key is found.
FIG. 3 depicts a Patricia tree 60. For clarity, the Patricia tree 60 is shown as testing only a relatively small number of bits. The Patricia tree 60 includes nodes 62, 64, 70 and 74, branches 63, 65, 66, 69, 71, 72, 75 and 76 and leaves 67, 68, 73, 77 and 78. The nodes 62, 64, 70 and 74 are where bits of the key are tested. The branches 63, 65, 66, 69, 71, 72, 76 and 76 represent pointers to the next bit to test and the value of the bit tested. The leaves 67, 68, 73, 77 and 78 represent stored addresses. The stored addresses at the leaves 67, 68, 73, 77 and 78 could be a full IP address having 32 bits or could be a prefix for an IP address, such as the address for the router used to connect to certain IP addresses. For example, the prefix might include only twenty-four bits. The stored addresses may include prefixes because a particular network processor 42 may have knowledge of only some of the components of the network 1. Using the stored addresses known by the network processor 42, the IP packet can be forwarded to a known point in the network that is close to the destination of the IP packet indicated by the key. Thus, a longest prefix match is used to ensure that the IP packet travels closer to the destination indicated by the key for the IP packet.
Using the Patricia tree 60, step 52 of the method 50 would be performed. Referring to FIGS. 2 and 3, a first bit in the key, bit A, is tested at node 62. If bit A is a one, then branch 63 is taken to node 64. Based on the test of bit B at the node 64, the address A1 or A2 is obtained as the longest prefix match. Thus, if bit B is a one, then the address A2 on leaf 68 is used. If bit B is a zero, then the address Al on the leaf 67 is used. The addresses A1 and A2 may be complete IP addresses, or may be prefixes. If it is determined that bit A at node 62 is a zero, then branch 69 is taken to node 70, where bit C is tested. If bit C is a one, then address A3 at leaf 73 is determined to be the longest prefix match for the key. If bit C is a zero, then bit D at node 74 is tested. If bit D is a zero then address A4 of leaf 77 is the longest prefix match. However, if bit D is a one, then address A5 of leaf 78 is determined to be the longest prefix match for the key. As discussed above, the address A1, A2, A3, A4 or A5 that is the longest prefix match may simply be a prefix for the key, rather than an exact match of the key.
Referring back to FIG. 2, once the longest prefix match of the key is found, the longest prefix match is used to forward the IP packet, via step 54. Thus, using the method 50, the longest prefix match for a particular key (IP address) of a packet is found. The longest prefix match could theoretically be as short as one bit or as long as the key when an exact match is found. The longest prefix match is then used to forward the IP packet to a point in the network that is closer to the destination of the IP packet. The method 50 can then be repeated by another component, such as another router or switch, to continue to move the IP packet closer to the destination. The method 50 can also be repeated by the network processor 42 for other IP packets traveling through the network 1.
Referring to FIGS. 1A, 1B, 2 and 3, although the method 50 using the Patricia tree 60 functions, one of ordinary skill in the art will readily recognize that there are drawbacks to performing the longest prefix match search using the method 50. The Patricia tree 60 requires a relatively large amount of memory, which is undesirable. The Patricia tree 60 actually includes only stored addresses, some of which are prefixes. However, space to store other complete IP addresses as well as other prefixes must also be allocated for the Patricia tree 60. For example, suppose the address A3 is a prefix having only twenty-four significant bits. In FIG. 3, all nodes, such as the nodes 62, 64, 70 and 74, must allow space to point to subsequent nodes and leaves. Leaves holding prefixes are usually very few and far between. Thus, the nodes 62 and 70 include prefixes 79 and 80, whereas nodes 64 and 74 contain empty space holders for prefixes. Providing this space consumes a relatively large amount of memory (not explicitly shown). One way to reduce space consumption when implementing the Patricia tree 60 and the method 50 is to use different node types, one type for nodes that contain prefixes as well as next node pointers when prefixes exist and another type for nodes that contain next node pointers without prefixes when prefixes do not exist. This makes implementation of the method 50 and the Patricia tree 60 more onerous for a developer.
Accordingly, what is needed is a system and method for forwarding an IP packet using a longest prefix match search. The present invention addresses such a need.